平衡完全二部图的子图多色边染色献给刘桂真教授80寿辰  

Polychromatic edge-colorings of subgraphs of balanced complete bipartite graphs

作　　者：张霞 蒋真真 张鑫淼 Xia Zhang;Zhenzhen Jiang;Xinmiao Zhang

机构地区：[1]山东师范大学数学与统计学院,济南250358

出　　处：《中国科学：数学》2024年第11期1889-1904,共16页Scientia Sinica：Mathematica

基　　金：国家自然科学基金(批准号:12071265)资助项目。

摘　　要：设G是一个图,W是G的一些子图的集合.对G的一个m色的边染色,若与W中元素同构的子图上都出现了所有的m种颜色,则称该边染色是G的一个m色W-多色边染色.本文通过揭示图的子图多色边染色问题与Turán问题的密切联系,研究平衡完全二部图Kn,n的W-子图多色边染色问题.当W是下列3种子图集合之一时:Hamilton圈、2-因子和K_(n-1),_(n-1),本文确定K_(n,n)的W-子图多色数的值分别是n+1、n+1和[n^(2)/3)].此外,当主图是Kn,n时,本文证明任意一个2-因子的Turán数是n^(2)-n+1.Let G be a graph and W be a set of some subgraphs of G.An m-edge-coloring of G is called W-polychromatic if every subgraph isomorphic to some element from W receives all m colors.In this paper,the close relationship between the subgraph polychromatic edge-coloring problem of graphs and the Turan problem is uncovered,and the W-polychromatic edge-coloring problem of the complete bipartite graph Kn;n is studied.We determine the exact value of the W-polychomatic number to be n+1,n+1,[n^(2)/3],respectively,when W is one of three sets of subgraphs of Kn;n:Hamilton cycles,2-factors,Kn1;n1's.Furthermore,when the host graph is Kn;n,we show that the Turan number of any 2-factor of Kn;n is n^(2)−n+1.

关 键 词：多色染色 多色子图 Turán数 超图 不交的横贯 

分 类 号：O157.5[理学—数学]