Odd coloring of sparse graphs and planar graphs
Let \(G=(V(G),E(G))\) be a graph and \(c:V(G)\rightarrow \{1,\dots,k\}\) a proper coloring, i. e., \(c(u)\neq c(v)\) for every \(uv\in E(G)\). If for every vertex \(v\) with a degree at least one there exists a color \(i_v\in\{1,\dots,k\}\) that appears an odd number of times in the neighborhood of \(v\), then we call \(c\) an odd coloring with \(k\) colors. Maximum average degree \(\mathrm{mad}(G)\) of \(G\) is the biggest average degree of any subgraph of \(G\). This contribution completely resolves Cranston's conjecture that in \(G\) there exists an odd coloring with \(k\geq 4\) colors if \(\mathrm{mad}(G)\leq\frac{4k-4}{k+1}\). This conjecture is disproved for \(k=4\), while for \(k\geq 7\) a stronger version of the conjecture is proved. (The conjecture is already known to be true for \(k\in\{5,6\}\).) Some additional results are given for planar graphs.
- The theorem of the complement for a quasi subanalytic set
- On the singular locus of sets definable in a quasianalytic structure
- Geometric and differential properties of subanalytic sets
- Closure and connected component of a planar global semianalytic set defined by analytic functions definable in o-minimal structure
- Geometric and differential properties of subanalytic sets
- Remarks on proper conflict-free colorings of graphs
- Colorings with neighborhood parity condition
- The odd chromatic number of a planar graph is at most 8
- A note on odd colorings of 1-planar graphs
- On the singular locus of sets definable in a quasianalytic structure
- Structure and Coloring of Graphs with Only Small Odd Cycles
- Odd edge coloring of graphs
- scientific article; zbMATH DE number 2060071 (Why is no real title available?)
- Odd 4-edge-colorability of graphs
- (r) does not imply (n) or (npf) for definable sets in nonpolynomially bounded o-minimal structures
- 1-planar graphs are odd 13-colorable
- Odd colourings, conflict-free colourings and strong colouring numbers
- On odd colorings of planar graphs
- An improvement of the bound on the odd chromatic number of 1-planar graphs
- On odd colorings of sparse graphs
- Odd-sum colorings of planar graphs
- Odd coloring of sparse graphs and planar graphs
- Improper odd coloring of IC-planar graphs
- Odd 4-coloring of outerplanar graphs
- Brooks-type theorems for relaxations of square colorings
- Odd colorings of sparse graphs
- Proper conflict-free coloring of sparse graphs
- New bounds for odd colourings of graphs
- New bounds for proper h-conflict-free colorings
- Odd coloring of 2-boundary planar graphs and beyond
- Boundedness for proper conflict-free and odd colorings
- The proper conflict-free k-coloring problem and the odd k-coloring problem are NP-complete on bipartite graphs
- On odd and strong odd colorings of graphs
- An improvement of the bound on the improper odd chromatic number of IC-planar graphs
- The forb-flex method for odd coloring and proper conflict-free coloring of planar graphs
- On the parameterized complexity of odd coloring
- On strong odd colorings of graphs
- An odd 4-coloring of a maximal outerplanar graph
- Tight bounds on odd chromatic number of some standard graph products
- Odd coloring of k-trees
- Strong odd coloring of sparse graphs
- On the parameterized complexity of odd coloring
- 2-odd coloring of graphs with small maximum average degree
- Odd coloring of planar graph based on local structural constraints
This page was built for publication: Odd coloring of sparse graphs and planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2689480)
