Equitable Coloring and Equitable Choosability of Graphs with Small Maximum Average Degree
A graph is said to be equitably k-colorable if the vertex set V (G) can be partitioned into k independent subsets V1, V2, . . . , Vk such that ||Vi|−|Vj || ≤ 1 (1 ≤ i, j ≤ k). A graph G is equitably k-choosable if, for any given k-uniform list assignment L, G is L-colorable and each color appears on...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Sciendo
2018-08-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | http://www.degruyter.com/view/j/dmgt.2018.38.issue-3/dmgt.2049/dmgt.2049.xml?format=INT |
| id |
doaj-art-16f7e7ec89bd4db7974c0c6b4f79a409 |
|---|---|
| recordtype |
oai_dc |
| spelling |
doaj-art-16f7e7ec89bd4db7974c0c6b4f79a4092018-08-24T17:59:30ZengSciendoDiscussiones Mathematicae Graph Theory2083-58922018-08-0138382983910.7151/dmgt.2049dmgt.2049Equitable Coloring and Equitable Choosability of Graphs with Small Maximum Average DegreeDong Aijun0Zhang Xin1School of Science, Shandong Jiaotong University, Jinan, 250023, P.R. ChinaSchool of Mathematics and Statistics, Xidian University, Xi’an, 710071, P.R. ChinaA graph is said to be equitably k-colorable if the vertex set V (G) can be partitioned into k independent subsets V1, V2, . . . , Vk such that ||Vi|−|Vj || ≤ 1 (1 ≤ i, j ≤ k). A graph G is equitably k-choosable if, for any given k-uniform list assignment L, G is L-colorable and each color appears on at most ⌈|V(G)|k⌉$\left\lceil {{{\left| {V(G)} \right|} \over k}} \right\rceil$ vertices. In this paper, we prove that if G is a graph such that mad(G) < 3, then G is equitably k-colorable and equitably k- choosable where k ≥ max{Δ(G), 4}. Moreover, if G is a graph such that 125${{12} \over 5}$ , then G is equitably k-colorable and equitably k-choosable where k ≥ max{Δ (G), 3}.http://www.degruyter.com/view/j/dmgt.2018.38.issue-3/dmgt.2049/dmgt.2049.xml?format=INTgraph coloringequitable choosabilitymaximum average degree05C15 |
| institution |
Open Data Bank |
| collection |
Open Access Journals |
| building |
Directory of Open Access Journals |
| language |
English |
| format |
Article |
| author |
Dong Aijun Zhang Xin |
| spellingShingle |
Dong Aijun Zhang Xin Equitable Coloring and Equitable Choosability of Graphs with Small Maximum Average Degree Discussiones Mathematicae Graph Theory graph coloring equitable choosability maximum average degree 05C15 |
| author_facet |
Dong Aijun Zhang Xin |
| author_sort |
Dong Aijun |
| title |
Equitable Coloring and Equitable Choosability of Graphs with Small Maximum Average Degree |
| title_short |
Equitable Coloring and Equitable Choosability of Graphs with Small Maximum Average Degree |
| title_full |
Equitable Coloring and Equitable Choosability of Graphs with Small Maximum Average Degree |
| title_fullStr |
Equitable Coloring and Equitable Choosability of Graphs with Small Maximum Average Degree |
| title_full_unstemmed |
Equitable Coloring and Equitable Choosability of Graphs with Small Maximum Average Degree |
| title_sort |
equitable coloring and equitable choosability of graphs with small maximum average degree |
| publisher |
Sciendo |
| series |
Discussiones Mathematicae Graph Theory |
| issn |
2083-5892 |
| publishDate |
2018-08-01 |
| description |
A graph is said to be equitably k-colorable if the vertex set V (G) can be partitioned into k independent subsets V1, V2, . . . , Vk such that ||Vi|−|Vj || ≤ 1 (1 ≤ i, j ≤ k). A graph G is equitably k-choosable if, for any given k-uniform list assignment L, G is L-colorable and each color appears on at most
⌈|V(G)|k⌉$\left\lceil {{{\left| {V(G)} \right|} \over k}} \right\rceil$
vertices. In this paper, we prove that if G is a graph such that mad(G) < 3, then G is equitably k-colorable and equitably k- choosable where k ≥ max{Δ(G), 4}. Moreover, if G is a graph such that
125${{12} \over 5}$
, then G is equitably k-colorable and equitably k-choosable where k ≥ max{Δ (G), 3}. |
| topic |
graph coloring equitable choosability maximum average degree 05C15 |
| url |
http://www.degruyter.com/view/j/dmgt.2018.38.issue-3/dmgt.2049/dmgt.2049.xml?format=INT |
| _version_ |
1612672596381270016 |