An Even 2-Factor in the Line Graph of a Cubic Graph
An even 2-factor is one such that each cycle is of even length. A 4- regular graph G is 4-edge-colorable if and only if G has two edge-disjoint even 2- factors whose union contains all edges in G. It is known that the line graph of a cubic graph without 3-edge-coloring is not 4-edge-colorable. Hence...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Georgia Southern University
2022-05-01
|
| Series: | Theory and Applications of Graphs |
| Subjects: | |
| Online Access: | https://digitalcommons.georgiasouthern.edu/tag/vol9/iss1/7/ |
| _version_ | 1828810225495310336 |
|---|---|
| author | SeungJae Eom Kenta Ozeki |
| author_facet | SeungJae Eom Kenta Ozeki |
| author_sort | SeungJae Eom |
| collection | DOAJ |
| description | An even 2-factor is one such that each cycle is of even length. A 4- regular graph G is 4-edge-colorable if and only if G has two edge-disjoint even 2- factors whose union contains all edges in G. It is known that the line graph of a cubic graph without 3-edge-coloring is not 4-edge-colorable. Hence, we are interested in whether those graphs have an even 2-factor. Bonisoli and Bonvicini proved that the line graph of a connected cubic graph G with an even number of edges has an even 2-factor, if G has a perfect matching [Even cycles and even 2-factors in the line graph of a simple graph, Electron. J. Combin. 24 (2017), P4.15]. In this paper, we extend this theorem to the line graph of a connected cubic graph G satisfying certain conditions. |
| first_indexed | 2024-12-12T09:08:40Z |
| format | Article |
| id | doaj.art-f33d7e66b2c44367b03f3f227b570ab4 |
| institution | Directory Open Access Journal |
| issn | 2470-9859 |
| language | English |
| last_indexed | 2024-12-12T09:08:40Z |
| publishDate | 2022-05-01 |
| publisher | Georgia Southern University |
| record_format | Article |
| series | Theory and Applications of Graphs |
| spelling | doaj.art-f33d7e66b2c44367b03f3f227b570ab42022-12-22T00:29:35ZengGeorgia Southern UniversityTheory and Applications of Graphs2470-98592022-05-01911910.20429/tag.2022.090107An Even 2-Factor in the Line Graph of a Cubic GraphSeungJae EomKenta OzekiAn even 2-factor is one such that each cycle is of even length. A 4- regular graph G is 4-edge-colorable if and only if G has two edge-disjoint even 2- factors whose union contains all edges in G. It is known that the line graph of a cubic graph without 3-edge-coloring is not 4-edge-colorable. Hence, we are interested in whether those graphs have an even 2-factor. Bonisoli and Bonvicini proved that the line graph of a connected cubic graph G with an even number of edges has an even 2-factor, if G has a perfect matching [Even cycles and even 2-factors in the line graph of a simple graph, Electron. J. Combin. 24 (2017), P4.15]. In this paper, we extend this theorem to the line graph of a connected cubic graph G satisfying certain conditions.https://digitalcommons.georgiasouthern.edu/tag/vol9/iss1/7/even 2-factorline graphedge colouring |
| spellingShingle | SeungJae Eom Kenta Ozeki An Even 2-Factor in the Line Graph of a Cubic Graph Theory and Applications of Graphs even 2-factor line graph edge colouring |
| title | An Even 2-Factor in the Line Graph of a Cubic Graph |
| title_full | An Even 2-Factor in the Line Graph of a Cubic Graph |
| title_fullStr | An Even 2-Factor in the Line Graph of a Cubic Graph |
| title_full_unstemmed | An Even 2-Factor in the Line Graph of a Cubic Graph |
| title_short | An Even 2-Factor in the Line Graph of a Cubic Graph |
| title_sort | even 2 factor in the line graph of a cubic graph |
| topic | even 2-factor line graph edge colouring |
| url | https://digitalcommons.georgiasouthern.edu/tag/vol9/iss1/7/ |
| work_keys_str_mv | AT seungjaeeom aneven2factorinthelinegraphofacubicgraph AT kentaozeki aneven2factorinthelinegraphofacubicgraph AT seungjaeeom even2factorinthelinegraphofacubicgraph AT kentaozeki even2factorinthelinegraphofacubicgraph |