Equitable coloring planar graphs with large girth (Q2470470): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 02:04, 3 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Equitable coloring planar graphs with large girth |
scientific article |
Statements
Equitable coloring planar graphs with large girth (English)
0 references
14 February 2008
0 references
An equitable coloring of a graph \(G\) is a proper vertex coloring such that the difference in size of every two color classes is at most one. The equitable threshold \(\chi_{\text{Eq}}^\ast(G)\) is the smallest integer \(m\) such that \(G\) has an equitable coloring using \(n\) colors for every \(n \geq m\). It is proved in this paper that \(\chi_{\text{Eq}}^\ast(G)=\chi(G)\) if \(G\) is a non-bipartite planar graph with girth at least 26 and minimum degree at least 2, or \(G\) is a 2-connected outerplanar graph with girth at least 4.
0 references
equitable coloring
0 references
planar graphs
0 references
outerplanar graphs
0 references
girth
0 references