Skip to main content
SpringerLink
Log in

Strong Edge Coloring of Outerplane Graphs with Independent Crossings

  • Published:
Acta Mathematicae Applicatae Sinica, English Series Aims and scope Submit manuscript

Abstract

The strong chromatic index of a graph is the minimum number of colors needed in a proper edge coloring so that no edge is adjacent to two edges of the same color. An outerplane graph with independent crossings is a graph embedded in the plane in such a way that all vertices are on the outer face and two pairs of crossing edges share no common end vertex. It is proved that every outerplane graph with independent crossings and maximum degree Δ has strong chromatic index at most 4Δ − 6 if Δ ≥ 4, and at most 8 if Δ ≤ 3. Both bounds are sharp.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Auer, C., Bachmaier, C., Brandenburg, F.J., Gleißner, A., Hanauer, K., Neuwirth, D., Reislhuber, J. Outer 1-planar graphs. Algorithmica, 74(4): 1293–1320 (2016)

    Article  MathSciNet  Google Scholar 

  2. Bonamy, M., Perrett, T., Postle, L. Colouring graphs with sparse neighbourhoods: Bounds and applications. arXiv: 1810.06704 (2018)

  3. Bonamy, M., Perrett, T., Postle, L. Colouring graphs with sparse neighbour-hoods: Bounds and applications. Journal of Combinatorial Theory, Series B, 155: 278–317 (2022)

    Article  MathSciNet  Google Scholar 

  4. Bruhn, H., Joos, F. A stronger bound for the strong chromatic index. Electronic Notes in Discrete Mathematics. The Eight European Conference on Combinatorics, Graph Theory and Applications, 49: 277–284 (2015)

    Google Scholar 

  5. Eggleton, R. Rectilinear drawings of graphs. Utilitas Mathematica, 29: 149–172 (1986)

    MathSciNet  Google Scholar 

  6. Faudree, R. J., Schelp, R.H., Gyárfás, A., Tuza, A. The strong chromatic index of graphs. Ars Combinatoria, 29B: 205–211 (1990)

    MathSciNet  Google Scholar 

  7. Fouquet, J. L., Jolivet, J. L. Strong edge-colorings of graphs and applications to multik-gons. Ars Combinatoria, 16A: 141–150 (1983)

    Google Scholar 

  8. Guo, Y., Zhang, X., Zhang, X. Strong edge-colorings of planar graphs with small girth. Communication on Applied Mathematics and Computation, 394: 125796 (2021)

    Article  MathSciNet  Google Scholar 

  9. Hocquard, H., Ochem, P., Valicov, P. Strong edge-colouring and induced matchings. Information Processing Letters, 113(19): 836–843 (2013)

    Article  MathSciNet  Google Scholar 

  10. Hong, S.H., Eades P., Katoh, N., Liotta, G., Schweitzer, P., Suzuki, Y. A linear-time algorithm for testing outer-1-planarity. Algorithmica, 72(4): 1033–1054 (2015)

    Article  MathSciNet  Google Scholar 

  11. Hurley, E., de Joannis de Verclos, R., Kang, R.J. An improved procedure for colouring graphs of bounded local density. In: Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2021, 135–148

  12. Liotta, G., Montecchiani, F. L-visibility drawings of IC-planar graphs. Information Processing Letters, 116(3): 217–222 (2016)

    Article  MathSciNet  Google Scholar 

  13. Liu, Z., Xu, C. Adjacent vertex distinguishing edge coloring of IC-planar graphs. Journal of Combinatorial Optimization, 43(4): 710–726 (2022)

    Article  MathSciNet  Google Scholar 

  14. Molloy, M., Reed, B. A bound on the strong chromatic index of a graph. Journal of Combinatorial Theory, Series B, 69(2): 103–109 (1997)

    Article  MathSciNet  Google Scholar 

  15. Niu, B., Zhang, X., Gao, Y. Equitable partition of plane graphs with independent crossings into induced forests. Discrete Mathematics, 343(5): 111792 (2020)

    Article  MathSciNet  Google Scholar 

  16. Song, W., Duan, Y., Wang, J., Miao, L. Acyclic edge coloring of IC-planar graphs. Acta Mathematicae Applicatae Sinica. English Series, 36(3): 581–589 (2020)

    Article  MathSciNet  Google Scholar 

  17. Wang, Y., Wang, P., Wang, W. Strong chromatic index of K4-minor free graphs. Information Processing Letters, 129: 53–56 (2018)

    Article  MathSciNet  Google Scholar 

  18. Xu, W., Zhang, X. The maximum size of an edge 2-neighborhood in P5-free graphs. Discrete Mathematicsh, 345(9): 112961 (2022)

    Article  Google Scholar 

  19. Yang, W., Wang, Y., Wang, W., Ko-Wei, L. IC-planar graphs are 6-choosable. SIAM Journal on Discrete Mathematics, 35(3): 1729–1745 (2021)

    Article  MathSciNet  Google Scholar 

  20. Zhang, X. Drawing complete multipartite graphs on the plane with restrictions on crossings. Acta Mathematica Sinica (English Series), 30: 2045–2053 (2013)

    Article  MathSciNet  Google Scholar 

  21. Zhang, X. Total coloring of outer-1-planar graphs with near-independent crossings. Journal of Combinatorial Optimization, 34: 661–675 (2017)

    Article  MathSciNet  Google Scholar 

  22. Zhang, X., Liu, G. The structure of plane graphs with independent crossings and its applications to coloring problems. Central European Journal of Mathematics, 11(2): 308–321 (2013)

    MathSciNet  Google Scholar 

  23. Zhang, X., Liu, G., Wu, J. Edge covering pseudo-outerplanar graphs with forests. Discrete Mathematics, 312(18): 2788–2799 (2012)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematics and Statistics, Xidian University, Xi’an, 710071, China

    Ke-Jie Li & Xin Zhang

Authors
  1. Ke-Jie Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xin Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xin Zhang.

Ethics declarations

The authors declare no conflict of interest.

Additional information

The project is supported by the Natural Science Basic Research Plan in Shaanxi Province of China (No. 2023-JC-YB-001) and the National Natural Science Foundation of China (No. 11871055).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, KJ., Zhang, X. Strong Edge Coloring of Outerplane Graphs with Independent Crossings. Acta Math. Appl. Sin. Engl. Ser. 40, 467–477 (2024). https://doi.org/10.1007/s10255-024-1026-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10255-024-1026-6

Keywords

2020 MR Subject Classification

Search

Navigation