Results 21 to 30 of about 745,346 (269)
Flexible list coloring of graphs with maximum average degree less than $3$ [PDF]
, 2023 In the flexible list coloring problem, we consider a graph $G$ and a color list assignment $L$ on $G$, as well as a subset $U \subseteq V(G)$ for which each $u \in U$ has a preferred color $p(u) \in L(u)$. Our goal is to find a proper $L$-coloring $ϕ$ of $G$ such that $ϕ(u) = p(u)$ for at least $ε|U|$ vertices $u \in U$. We say that $G$ is $ε$-flexibly
Richard Bi, Peter Bradshaw
openalex +3 more sources
Coloring the squares of graphs whose maximum average degrees are less than 4 [PDF]
, 2015 The square $G^2$ of a graph $G$ is the graph defined on $V(G)$ such that two vertices $u$ and $v$ are adjacent in $G^2$ if the distance between $u$ and $v$ in $G$ is at most 2. The {\em maximum average degree} of $G$, $mad (G)$, is the maximum among the average degrees of the subgraphs of $G$. It is known in \cite{BLP-14-JGT} that there is no constant $
Seog‐Jin Kim, Boram Park
openalex +3 more sources
On the Neighbour Sum Distinguishing Index of Graphs with Bounded Maximum Average Degree [PDF]
Graphs and Combinatorics, 2017 A proper edge $k$-colouring of a graph $G=(V,E)$ is an assignment $c:E\to \{1,2,\ldots,k\}$ of colours to the edges of the graph such that no two adjacent edges are associated with the same colour. A neighbour sum distinguishing edge $k$-colouring, or nsd $k$-colouring for short, is a proper edge $k$-colouring such that $\sum_{e\ni u}c(e)\neq \sum_{e ...
H. Hocquard, J. Przybyło
openalex +4 more sources
Nordhaus-Gaddum-type theorems for maximum average degree [PDF]
46 ...
Yair Caro, Źsolt Tuza
openalex +3 more sources
(d,1)‐total labeling of graphs with a given maximum average degree [PDF]
Journal of Graph Theory, 2005 AbstractThe (d,1)‐total number $\lambda _{d}^{T}(G)$ of a graph G is the width of the smallest range of integers that suffices to label the vertices and the edges of G so that no two adjacent vertices have the same color, no two incident edges have the same color, and the distance between the color of a vertex and its incident edges is at least d.
Mickaël Montassier, André Raspaud
openalex +3 more sources
On the total neighbour sum distinguishing index of graphs with bounded maximum average degree [PDF]
Journal of Combinatorial Optimization, 2018 A proper total $k$-colouring of a graph $G=(V,E)$ is an assignment $c : V \cup E\to \{1,2,\ldots,k\}$ of colours to the edges and the vertices of $G$ such that no two adjacent edges or vertices and no edge and its end-vertices are associated with the same colour.
Hervé Hocquard, Jakub Przybyło
openalex +5 more sources
Cliques in squares of graphs with maximum average degree less than 4 [PDF]
Journal of Graph TheoryAbstractHocquard, Kim, and Pierron constructed, for every even integer , a 2‐degenerate graph with maximum degree such that . We prove for (a) all 2‐degenerate graphs and (b) all graphs with , upper bounds on the clique number of that match the lower bound given by this construction, up to small additive constants.
Daniel W. Cranston, Gexin Yu
openalex +3 more sources
Graphs with maximum degree D at least 17 and maximum average degree less than 3 are list 2-distance (D+2)-colorable [PDF]
, 2013 For graphs of bounded maximum average degree, we consider the problem of 2-distance coloring. This is the problem of coloring the vertices while ensuring that two vertices that are adjacent or have a common neighbor receive different colors. It is already known that planar graphs of girth at least 6 and of maximum degree D are list 2-distance (D+2 ...
Marthe Bonamy +2 more
openalex +3 more sources
Linear and 2-Frugal Choosability of Graphs of Small Maximum Average Degree [PDF]
Graphs and Combinatorics, 2011 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Nathann Cohen, Frédéric Havet
openalex +4 more sources
Graphs of maximum average degree less than $\frac {11}{3}$ are flexibly $4$-choosable [PDF]
We consider the flexible list coloring problem, in which we have a graph $G$, a color list assignment $L:V(G) \rightarrow 2^{\mathbb N}$, and a set $U \subseteq V(G)$ of vertices such that each $u \in U$ has a preferred color $p(u) \in L(u)$. Given a constant $\varepsilon > 0$, the problem asks for an $L$-coloring of $G$ in which at least ...
Richard Bi, Peter Bradshaw
openalex +3 more sources