Acyclic 6-Colouring of Graphs with Maximum Degree 5 and Small Maximum Average Degree [PDF]
Discussiones Mathematicae Graph Theory, 2013 A k-colouring of a graph G is a mapping c from the set of vertices of G to the set {1, . . . , k} of colours such that adjacent vertices receive distinct colours.
Fiedorowicz Anna
doaj +3 more sources
8-star-choosability of a graph with maximum average degree less than 3 [PDF]
Discrete Mathematics & Theoretical Computer Science, 2011 Graphs and ...
Min Chen, André Raspaud, Weifan Wang
doaj +5 more sources
Graphs with Bounded Maximum Average Degree and Their Neighbor Sum Distinguishing Total-Choice Numbers [PDF]
International Journal of Mathematics and Mathematical Sciences, 2017 Let G be a graph and ϕ:V(G)∪E(G)→{1,2,3,…,k} be a k-total coloring. Let w(v) denote the sum of color on a vertex v and colors assigned to edges incident to v.
Patcharapan Jumnongnit +1 more
doaj +3 more sources
Equitable cluster partition of graphs with small maximum average degree
Discussiones Mathematicae Graph TheorySummary: An equitable \(\underbrace{({\mathcal{O}}_k, {\mathcal{O}}_k, \ldots, {\mathcal{O}}_k)}_m\)-partition of a graph \(G\), which is also called an equitable \(k\) cluster \(m\)-partition, is the partition of \(V(G)\) into \(m\) non-empty subsets \(V_1, V_2\), \ldots, \(V_m\) such that for every integer \(i\) in \(\{1, 2, \ldots, m\}\), \(G[V_i]\)
Xiaoling Liu, Lei Sun, Wei Zheng
doaj +3 more sources
Neighbor Distinguishing Colorings of Graphs with the Restriction for Maximum Average Degree [PDF]
Axioms, 2023 Neighbor distinguishing colorings of graphs represent powerful tools for solving the channel assignment problem in wireless communication networks. They consist of two forms of coloring: neighbor distinguishing edge coloring, and neighbor distinguishing ...
Jingjing Huo +3 more
doaj +3 more sources
On the maximum average degree and the incidence chromatic number of a graph [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 We prove that the incidence chromatic number of every 3-degenerated graph G is at most Δ(G)+4. It is known that the incidence chromatic number of every graph G with maximum average degree mad(G)<3 is at most Δ (G)+3.
Mohammad Hosseini Dolama, Eric Sopena
doaj +4 more sources
The average degree of edge chromatic critical graphs with maximum degree seven [PDF]
Journal of Graph Theory, 2023 AbstractIn this paper, by developing several new adjacency lemmas about a path on four or five vertices, we show that the average degree of 7‐critical graphs is at least 6. It implies Vizing's planar graph conjecture for planar graphs with maximum degree 7 and its extension to graphs embeddable in a surface with nonnegative Euler characteristic due to ...
Yan Cao +3 more
+6 more sources
The chromatic number of signed graphs with bounded maximum average degree [PDF]
Discrete Applied Mathematics, 2022 A signed graph is a simple graph with two types of edges: positive and negative edges. Switching a vertex $v$ of a signed graph corresponds to changing the type of each edge incident to $v$. A homomorphism from a signed graph $G$ to another signed graph $H$ is a mapping $ : V(G) \rightarrow V(H)$ such that, after switching some of the vertices of $G$,
Fabien Jacques, Alexandre Pinlou
openalex +6 more sources
Maximum average degree of list-edge-critical graphs and Vizing's conjecture [PDF]
Electronic Journal of Graph Theory and Applications, 2022 Summary: Vizing conjectured that \(\chi^\prime_\ell(G) \leq \Delta + 1\) for all graphs. For a graph \(G\) and nonnegative integer \(k\), we say \(G\) is a \(k\)-list-edge-critical graph if \(\chi^\prime_\ell (G)>k\), but \(\chi^\prime_\ell(G-e)\leq k\) for all \(e \in E(G)\).
Joshua Harrelson, Hannah Reavis
openalex +2 more sources
Incidence coloring of graphs with high maximum average degree [PDF]
Discrete Applied Mathematics, 2017 An incidence of an undirected graph G is a pair $(v,e)$ where $v$ is a vertex of $G$ and $e$ an edge of $G$ incident with $v$. Two incidences $(v,e)$ and $(w,f)$ are adjacent if one of the following holds: (i) $v = w$, (ii) $e = f$ or (iii) $vw = e$ or $f$.
Marthe Bonamy +3 more
openalex +3 more sources